package mo.structure;

public class Heap {

    private int[] a = null;
    private int size = 0;
    private int used = 0;

    public Heap(int[] a, int size) {
        this.a = new int[size];
        this.size = size;
    }

    private void sink(int i) {
        int j = 0;
        int t = a[i];
        while ((j = (i << 1) + 1) < size) {

            //左右子节点都比较
            if (j < size -1 && a[j] < a[j+1]) {
                j++;
            }

            if (a[j] > t) {
                a[i] = a[j];
                i = j;
            } else {
                break;
            }
        }
        a[i] = t;
    }

    private void swim(int i) {
        int t = a[i];
        int par = 0;
        while (i > 0 && (par = (i - 1) >> 1) != i) {
            if (a[par] < t) {
                a[i] = a[par];
                i = par;
            } else {
                break;
            }
        }
        a[i] = t;
    }

    public void push(int v) {
        a[used++] = v;
        swim(used -1);
    }

    public int pop() {
        int ret = a[0];
        a[0] = a[--used];
        sink(0);
        return ret;
    }

    public int size() {
        return used;
    }
}
